package Q144;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树的前序遍历
 *
 * @author 23737
 * @time 2021.11.25
 */
public class Test {
    public static void main(String[] args) {

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * dfs深搜
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if (root == null) {
            return arrayList;
        }
        dfs(root,arrayList);
        return arrayList;
    }

    private void dfs(TreeNode root, ArrayList<Integer> arrayList) {
        if (root == null) {
            return;
        }
        arrayList.add(root.val);
        dfs(root.left,arrayList);
        dfs(root.right,arrayList);
    }
}

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution2 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            // 这里一定要注意 用迭代法进行遍历的时候，先要添加右结点，再添加左结点。
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

